
public class BinarySerch {

    public static void main(String[] args) {
        int[] data =  {-4, 1, 2, 2, 5, 5, 5,8, 10};
		int value = 6;
        int find = binarySearch(data,value);
        if (find != -1) {
            System.out.println("the location index is " + find + ";the value is " + data[find]);
        } else {
            System.out.println("the situation not exist");
        }
    }

    /**
     * 使用二分查找， 找到 小于等于 t的最后一个数 
     * @param data
     * @param value
     */
    public static int binarySearch(int[] data,int value) {
        if (data == null || data.length == 0) {
            return -1;
        }
        int low = 0;
        int high = data.length-1;
        int middle = low + (high-low)/2;
        while(middle > low && middle < high) {
            //System.out.println("low:" + low + ";middle:" + middle + ";high:" + high);
            if (data[middle] > value) {
                high = middle;
            } else if (data[middle] <= value) {
                low = middle;
            }
            middle = low + (high-low)/2;
        }
        //System.out.println("--- low:" + low + ";middle:" + middle + ";high:" + high);
        if (middle == low ) {
            //只剩下 1 到 2个元素时
            if (middle == high && data[middle] <= value) {
                // 1个元素
                return middle;
            }
            //2 个元素
            if (data[high] <= value) {
                return high;
            }
            if (data[low] <= value) {
                return low;
            }
        }
        return -1;
    }
}
